package solution._0000._0004;

/**
 * Created by chen_snow
 * Date: 2021/4/27 22:48
 * Description:
 */
public class Solution {

    public static void main(String[] args) {
        int[] num1 = {1, 3};
        int[] num2 = {2};
        System.out.println(findMedianSortedArrays(num1, num2
        ));
    }

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length = nums1.length + nums2.length;

        /**
         * 偶数： 取中间两个数，求平均
         * 奇数： 取最中间一个数
         */
        if (length % 2 == 0) {
            return (findKthNum(nums1, nums2, 0, 0, length / 2 + 1)
                    + findKthNum(nums1, nums2, 0, 0, length / 2)) / 2;
        } else {
            return findKthNum(nums1, nums2, 0, 0, length / 2 + 1);
        }
    }

    /**
     *
     * @param nums1 数组1
     * @param nums2 数组2
     * @param start1 数组1的开始位置
     * @param start2 数组2的开始位置
     * @param K 第K大数
     * @return
     */
    public static double findKthNum(int[] nums1, int[] nums2, int start1, int start2, int K) {

        if (start1 == nums1.length) {
            return nums2[start2 + K - 1];
        } else if (start2 == nums2.length) {
            return nums1[start1 + K - 1];
        } else if (K == 1) {
            return Math.min(nums1[start1], nums2[start2]);
        }

        int length = K / 2;
        int index1 = Math.min(start1 + length, nums1.length) - 1;
        int index2 = Math.min(start2 + length, nums2.length) - 1;

        if (nums1[index1] >= nums2[index2]) {
            K = K - (index2 + 1 - start2);
            start2 = index2 + 1;
        } else {
            K = K - (index1 + 1 - start1);
            start1 = index1 + 1;
        }

        return findKthNum(nums1, nums2, start1, start2, K);

    }
}
